课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲的主题是整型数的其他操作以及指针的内容。

整型

加法

无符号加法

  • 无符号加法的方式为按正常加法运算，然后不考虑溢出位

  • 最终的结果为取模运算

可视化（数学）整数加法

  • 整数加法
    • 输入为$4$比特的整数$u,v$
    • 计算真实结果$\operatorname{Add}_{4}(u, v)$
    • 结果和$u,v$呈线性关系
    • 形成平面
可视化无符号加法

检查无符号加法的溢出

假设$u,v$为无符号整数，$s=u+v$，那么当且仅当$s<u$（或等价的$s<v$）时产生溢出，这是因为

补码加法

  • TAdd和UAdd比特级别行为相同，具体如下

    • ```c
      int s, t, u, v;
      s = (int) ((unsigned) u + (unsigned) v);
      t = u + v

      
  - 最后的结果是s==t

计算公式如下
$$
\text {TAdd}_{w}(u, v)=\text{U2T}_w\left(\text{UAdd}_{w}(\text{T2U}_w(u), \text{T2U}_w(v))\right)
$$



##### TAdd溢出

- 真实的加法需要$w+1$比特
- 处理方法为不考虑最高位
- 将其余的比特视为补码

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050506.jpg?raw=true)



##### 可视化补码加法

对补码加法进行可视化

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050507.jpg?raw=true)

- 值
  - 4比特的补码
  - 范围从$-8$到$7$
- 截断方法
  - 如果和$\ge 2^{w-1}$
    - 变成负数
  - 如果和$<-2^{w-1}$
    - 变成正数

公式如下
$$
x+ y=\left\{\begin{array}{ll}
x+y-2^{w}, & 2^{w-1} \leqslant x+y \\
x+y, & -2^{w-1} \leqslant x+y<2^{w-1} \\
x+y+2^{w}, & x+y<-2^{u-1}
\end{array}\right.
$$

如果画图表示则为：

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050817.jpg?raw=true)



##### 检查补码加法的溢出

利用上述公式可得如下结论：对于满足$\operatorname{TMin}_{w} \leqslant x,  y \leqslant \text{TMax}_{w}$的$x,y$，记$s=x+y$。如果$x>0,y>0$且$s<0$，则发生了正溢出；如果$x<0,y<0$且$s\ge0$，发生了负溢出。



#### 求反

##### 方法1

- 假设输入为$x$，我们希望得到$-x$
- 方式为对比特向量取反然后加$1$

证明如下：
$$
B 2 T_w(X)=-x_{w-1} \cdot 2^{w-1}+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}
$$
取反
$$
\begin{aligned}
-(1-x_{w-1}) \cdot 2^{w-1}+\sum_{i=0}^{w-2} (1-x_{i}) \cdot 2^{i}
&= -2^{w-1} + \sum_{i=0}^{w-2} 2^{i} +x_{w-1} \cdot 2^{w-1}-\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}\\
&=-1+x_{w-1} \cdot 2^{w-1}-\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}
\end{aligned}
$$
加$1$得到
$$
x_{w-1} \cdot 2^{w-1}-\sum_{i=0}^{w-2} x_{i} \cdot 2^{i} =-B2T_w(X)
$$

不难看出我们有
$$
-\text{TMin}=\text{TMin}
$$



##### 方法2

还有另一种求$-x$的方式，假设
$$
x=\left[x_{w-1},\cdots,x_0\right]
$$
令$k$是$x$最右边的$1$的位置，即
$$
x=\left[x_{w-1}, x_{w-2}, \cdots, x_{k+1}, 1,0, \cdots, 0\right]
$$
那么
$$
-x=\left[1-x_{w-1},1- x_{w-2}, \cdots, 1-x_{k+1}, 1,0, \cdots, 0\right]
$$
证明：

首先
$$
\begin{aligned}
B 2 T_w(X)&=-x_{w-1} \cdot 2^{w-1}+\sum_{i=k+1}^{w-2} x_{i} \cdot 2^{i} +2^{k}\\
\end{aligned}
$$
其次
$$
\begin{aligned}
&-(1-x_{w-1}) \cdot 2^{w-1}+\sum_{i=k+1}^{w-2} (1-x_{i}) \cdot 2^{i} +2^{k}\\
=&-2^{w-1} + 2^{k+1}(2^{w-k-2} -1) +x_{w-1} \cdot 2^{w-1}-\sum_{i=k+1}^{w-2} x_{i} \cdot 2^{i} + 2^{k}\\
=&x_{w-1} \cdot 2^{w-1}-\sum_{i=k+1}^{w-2} x_{i} \cdot 2^{i} -2^k\\
=&-B 2 T_w(X)
\end{aligned}
$$



#### 乘法

- 目标：计算$ w $位数字$ x，y $的乘积
  
  - 对于有符号或者无符号整型
  
- 但是，确切的结果可能大于$ w $位
  
    - 无符号：最多$ 2 w $位
    
        -  结果范围：
            $$
            0 \leq x{*} y \leq\left(2^{w}-1\right)^{2}=2^{2 w}-2^{w+1}+1
            $$
    
    - 二进制补码最小值（负数）：最多$ 2 w-1 $
      
        -  结果范围：
            $$
            x{*} y \geq\left(-2^{w-1}\right){*}\left(2^{w-1}-1\right)=-2^{2 w-2}+2^{w-1}
            $$
        
    - 二进制补码最大值（正）：最多$ 2 w $位，为$\left(\text{TMin}_{w}\right)^{2}$
    
        - 结果范围：
            $$
            xy \leq\left(-2^{w-1}\right)^{2}=2^{2 w-2}
            $$

- 所以，如果要保持准确结果
  
    - 计算每种乘法时都需要增加比特位
    - 在软件中完成（如果需要）



##### C中无符号乘法

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050508.jpg?raw=true)

- 标准乘法

  - 忽略高于$w$比特的部分

- 最终的结果为取模运算
  $$
  \text { UMult}_{w}(u, v)=u \cdot v \bmod 2^{w}
  $$
  



##### C中有符号乘法

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050509.jpg?raw=true)

- 标准乘法
  - 忽略高于$w$比特的部分
  - 有符号和无符号部分有些不同
  - 低位部分相同

计算公式为
$$
\text{TMult}_w(u,v)=U2T_w((u.v) \mod  2^w)
$$
其中$u.v$表示数学乘法。



##### 使用移位操作代替乘以2的幂

- 操作

  - $u<<k$给出$u\times 2^k$（有符号乘法和无符号乘法均成立）
  - ![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050510.jpg?raw=true)

- 例子

  - ```c
    u << 3 == u * 8

    • ```c
      (u << 5) – (u << 3) == u * 24

      
  - 大多数机器中左移比乘法快

    - 编译器会自动生成这样的代码

方法的证明：

假设$x$的$w$位二进制表示为$\left[
x_{w-1}  ,  x_{w-2}  \cdots  x_{0}
\right]$，那么$\left[x_{w-1}, x_{w-2}, \cdots, x_{0}, 0, \cdots, 0\right]$给出了$x2^k$的$w+k$位二进制表示：
$$
\begin{aligned}
B 2 U_{w+k}\left(\left[x_{w-1}, x_{w-2}, \cdots, x_{0}, 0, \cdots, 0\right]\right) &=\sum_{i=0}^{w-1} x_{i} 2^{i+k} \\
&=\left[\sum_{i=0}^{w-1} x_{i} 2^{i}\right] \cdot 2^{k} \\
&=x 2^{k}
\end{aligned}
$$
对于固定长度的表示，高$k$位被丢弃，左移$k$位的二进制表示为
$$
\left[x_{w-k-1}, x_{w-k-2}, \cdots, x_{0}, 0, \cdots, 0\right]
$$
所以
$$
\begin{aligned}
B 2 U_{w}\left(\left[x_{w-k-1}, x_{w-k-2}, \cdots, x_{0}, 0, \cdots, 0\right]\right) 
&=\sum_{i=0}^{w-k-1} x_{i} 2^{i+k} \\
&=\left[\sum_{i=0}^{w-k-1} x_{i} 2^{i}\right] \cdot 2^{k} \\
&=\left[\sum_{i=0}^{w-1} x_{i} 2^{i}\right] \cdot 2^{k} \mod 2^w \\
&=x2^k \mod 2^w
\end{aligned}
$$
所以对于无符号整数
$$
B 2 U_{w}\left(\left[x_{w-k-1}, x_{w-k-2}, \cdots, x_{0}, 0, \cdots, 0\right]\right)  = \text{UMult}_w(x,2^k)
$$
对于有符号整数，利用
$$
\text{TMult}_w(u,v)=U2T_w((u.v) \mod  2^w)
$$
可以得到相同的结果。



##### 一般情形

现在考虑一般的情形，假设我们需要计算$u\times K$，其中$K$为常数，将$K$表达为一组$0$和$1$交替的序列
$$
[(0 \cdots 0)(1 \cdots 1)(0 \cdots 0) \cdots(1 \cdots 1)]
$$
考虑一组从位置$n$到位置$m$的连续$1$，那么可以用如下方式计算这部分的对于乘积的影响：
$$
\begin{aligned}
&(x<<n)+(x<<(n-1))+\cdots+(x<<m)\\
&(x<<(n+1))-(x<<m)
\end{aligned}
$$



##### 使用移位操作代替除以2的幂（无符号）

- $u>>k$给出$\left\lfloor\text { u } / 2^{k}\right\rfloor$
- 使用逻辑移位

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050511.jpg?raw=true)

证明：

假设$x$的$w$位二进制表示为$\left[
x_{w-1}  ,  x_{w-2}  \cdots  x_{0}
\right]$，右移$k$位的二进制表示为$\left[
0, \cdots ,0 ,x_{w-1}  ,  x_{w-2}  \cdots  x_{w-k}
\right]$
$$
\begin{aligned}
B2U_w(\left[
0, \cdots ,0 ,x_{w-1}  ,  x_{w-2} , \cdots  ,x_{k}
\right])&= \sum_{i=0}^{w-k-1} x_{i+k} 2^{i} \\
B 2 U_{w}\left(\left[x_{w-1}, x_{w-2}, \cdots, x_{0}\right]\right) 
&=\sum_{i=0}^{w-1} x_{i} 2^{i} \\
&=2^k\sum_{i=0}^{w-k-1} x_{i+k} 2^{i}  +   \sum_{i=0}^{k-1} x_{i} 2^{i}\\
&= 2^k B2U_w(\left[
0, \cdots ,0 ,x_{w-1}  ,  x_{w-2} , \cdots  ,x_{k}
\right]) + \sum_{i=0}^{k-1} x_{i} 2^{i}
\end{aligned}
$$
所以
$$
\left\lfloor x / 2^{k}\right\rfloor = x >>k
$$



##### 使用移位操作代替除以2的幂（有符号）

- $u>>k$给出$\left\lfloor\text { u } / 2^{k}\right\rfloor$
- 使用算数移位

当$u>0$时上述方法和无符号情形一致，但是当$u<0$时则会产生有问题的结果，例如取$u=-12340$：

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture3/2020050512.jpg?raw=true)

考虑$k=4,8$时的结果，在C语言中实际结果为$-771$和$-48$，之所以和C语言中的结果不同，是因为上述算法朝着离$0$更远的方向舍入，所以当$u<0$时要向上舍入，达到上述效果利用如下事实即可
$$
\lceil x / y\rceil=\lfloor(x+y-1) / y\rfloor
$$
在此问题下使用如下方式即可，注意这里$y=2^k$

- $(u+(1<<k)-1)>>k$

C代码如下

```c
(x<0 ? x+(1<<k)-1 : x) >> k

总结

  • 加法：
    • 无符号/有符号：正常加法，然后截断，在位级别上相同的操作
    • 无符号：加法$\bmod 2^{w}$
      • 数学加法+可能减去$2^{w}$
    • 有符号：修改的加法$\bmod 2^{w}$（在适当范围内）
      • 数学加法和可能减去或加上$2^{w}$
  • 乘法：
    • 无符号/有符号：普通乘法后截断，在位级别上进行相同的操作
    • 无符号：乘法$\bmod 2^{w}$
    • 有符号：修改后的乘法$\bmod 2^{w}$（在适当范围内）
一些例子
例1
unsigned i;
for (i = cnt-2; i >= 0; i--)
	a[i] += a[i+1];

上述代码会死循环，因为无符号整数永远$\ge 0$，$0-1 \rightarrow \text{UMax}$，正确方式如下

unsigned i;
for (i = cnt-2; i < cnt; i--)
	a[i] += a[i+1];
例2
#define DELTA sizeof(int)
int i;
for (i = CNT; i-DELTA >= 0; i-= DELTA)
. . .

上述代码也会死循环，因为DELTA是无符号整数，赋值时会被强制转换成无符号整数。

正确方式如下：

size_t i;
for (i = cnt-2; i < cnt; i--)
	a[i] += a[i+1];
何时使用无符号整数
  • 在执行模块化算术时使用
    • 多精度算术
  • 在使用位表示集时使用
    • 逻辑右移，无符号扩展

内存中的表示形式，指针，字符串

面向字节的内存组织

  • 程序根据地址引用数据
    • 从概念上讲，可以将其设想为非常大的字节数组
      • 实际上不是，但是可以这样想
    • 地址就像是该数组的索引
      • 并且指针变量存储一个地址
    • 注意：系统为每个“进程”提供专用地址空间
    • 将进程视为正在执行的程序
    • 因此，程序可以破坏自己的数据，但不能破坏其他数据

Machine Words

  • 任何给定的计算机都具有“字长”
    • 整型数据（地址）的标称大小
    • 直到最近，大多数机器都使用32位（4字节）作为字长
      • 地址限制为4GB($2^{32}$比特)
    • 越来越多的机器具有64位字长
      • 可能有$18.4\times 10^{18}$个地址
    • 机器仍支持多种数据格式
      • 字长的分数或整数倍
      • 但总是整数比特

来看一个具体例子：

比特顺序

比特顺序分为大端法和小端法，考虑变量$x$，其值为$0\text{x} 01234567$，地址为$0\text{x}100$，大端法和小端法的表示区别为：

表示字符串

  • C中字符串
    • 用字符数组表示
    • 每个字符均以ASClI码表示
      • ASClI码是字符集的标准7位编码
      • 字符“0”的代码为0x30
        • 数字$ i $的代码为0x30+i
    • 字符串应以空值结尾
      • 最终字符= 0
  • 兼容性
    • 比特顺序不是问题

习题

初始化

int x = foo();
int y = bar();
unsigned ux = x;
unsigned uy = y;

这里假设int用32字节表示。

1.

错误，反例如下

2.

正确，因为$\mathbf{ux}$是无符号整数。

3.

正确，因为$\mathbf x \& 7$表示$\mathbf x$的最后三位为$1$，所以左移30位后第一位仍然为$1$

4.

错误，$-1$的二进制表示为全$1$，$\mathbf {ux}$将其转换为无符号整数，即$\text{UMax}$。

5.

错误，取$\mathbf y = \text{TMin}$，利用$-\mathbf y=\text{TMin}$

6.

错误，取较大$\mathbf x$就会产生错误。

7.

错误，正溢出。

8.

正确，因为每个正数对对应一个负数。

9.

错误，取$\mathbf x =\text{TMin}$

10.

错误，例如取$\mathbf x =0$，那么得到的结果为$0$。注意取非零$\mathbf x$，上述结论均成立，因为$\mathbf x |-\mathbf x$第一位一定是$1$，右移$31$位后会得到全部为$1$的二进制数，即$-1$

11.

正确。

12.

不正确，例如$x$取负数的时候。

13.

错误，取$\mathbf x = \text{TMin}=[1,0,\ldots, 0]$，那么$\mathbf x -1= [0,1,\ldots, 1]$，所以